# -*- encoding: utf-8 -*-
"""
Misclassification Error算法：
1. 分别根据每个特征不同值之间占比，求出每个特征的error
2. 根据error最小值找出最优划分特征
4. 以此类推递归计算每个子数据集并创建递归树，直到分类标签只有一个值
5. 测试递归树
"""


def calculate_error(dataset, feature):
    """计算数据集的Misclassification Error"""
    max_prob = 0.0
    # 获取分类标签
    cls_list = [example[feature] for example in dataset]
    cls_set = set(cls_list)
    for c in cls_set:
        prob = cls_list.count(c) / len(cls_list)
        if prob > max_prob:
            max_prob = prob
    return 1 - max_prob


def split_dataset(dataset, index, value):
    """根据特征值划分数据集"""
    sub_dataset = []
    for data in dataset:
        if data[index] == value:
            sub_dataset.append(data[:index] + data[index + 1:])
    return sub_dataset


def find_best_feature(dataset):
    """找出最好的特征，使得根据该特征划分后的gini split达到最小"""
    min_error = 100
    best_feature_index = -1
    feature_count = len(dataset[0]) - 1
    for i in range(feature_count):
        error = calculate_error(dataset, i)
        if error < min_error:
            min_error = error
            best_feature_index = i
    return best_feature_index
